软考真题
首页
题库
登录
第40题
最大尺寸和问题描述为,在n个整数(包含负数)的 数组 A中,求之和最大的非空连续子 数组 ,如 数组 A=(-2,11,-4,13,-5,-2) ,其中子 数组 B=(11,-4,13)具有最大子段和20(11-4+13=20) 。求解该问题时,可以将 数组 分为两个n/2个整数的子 数组 最大子段或或者在前半段,或者在后半段,或者跨越中间元素,通过该方法继续划分问题,直至最后求出最大子段和,该算法的时间复杂度为
( )
。
A.
O(nlgn)
B.
O(n
2
)
C.
O(n
2
lgn)
D.
O(n
3
)
答题卡
加油
计算器
纠错
草稿纸
得分:0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75